package lc.q51_100;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
 */
public class Q54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> num = new LinkedList<>();
        if (matrix.length == 0) {
            return num;
        }
        // 先走最外层
        // 再走里面一层
        // 再走在里面一层
        // 定义层数是i
        int k = 0;
        for (int level = 0; level * 2 < Math.max(matrix.length, matrix[0].length); level++) {
            // 顺时针走一圈
            for (int i = level; i < matrix[0].length - level && k < matrix.length * matrix[0].length; i++) {
                num.add(matrix[level][i]);
                k ++;
            }
            for (int i = level + 1; i < matrix.length - level && k < matrix.length * matrix[0].length; i++) {
                num.add(matrix[i][matrix[0].length - level - 1]);
                k ++;
            }
            for (int i = matrix[0].length - level - 2; i >= level && k < matrix.length * matrix[0].length; i--) {
                num.add(matrix[matrix.length - level - 1][i]);
                k ++;
            }
            for (int i = matrix.length - level - 2; i > level && k < matrix.length * matrix[0].length; i--) {
                num.add(matrix[i][level]);
                k ++;
            }
        }
        // 可能还未走完或者走多了,所以应该拿个东西记住
        return num;
    }

    public static void main(String[] args) {
        int[][] nums = {
                {1, 2, 3, 4},
                {1, 2, 3, 4},
                {1, 2, 3, 4},
                {1, 2, 3, 4},
                {1, 2, 3, 4}
        };
        System.out.println(new Q54().spiralOrder(nums));
    }
}
